package com.itheima.algorithm.recursion_single;

import java.util.Arrays;

/**
 * @author tantao
 * @version 1.0
 * @description: 斐波拉契数列1.618^n 算法时间复杂度：O(1)  <  O(logN)  <  O(n)  <  O(nlogN)  <  O(n^2)  <  O(n^3)  <  O(2^n)  <  O(n!)
 * @date 2025/8/19 17:09
 */
public class E06Fibonacci {


    public static void main(String[] args) {
        int[] cache = new int[31];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        System.out.println(fibonacci(30,cache ));
    }

    //多路递归
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }


    public static int fibonacci2(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0;
        int b = 1;
        int c = 1;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    public static int fibonacci(int n, int[] cache) {
        if (n <= 1) {
            return n;
        }
        //从缓存中获取结果
        int c1 = cache[n - 1];
        int x = 0;
        if (c1 != -1) {
            //缓存中有结果
            x = c1;
        } else {
            //缓存中没有结果
            x = fibonacci(n - 1, cache);
            //缓存结果
            cache[n - 1] = x;
        }

        //从缓存中获取结果
        int c2 = cache[n - 2];
        int y = 0;
        if (c2 != -1) {
            //缓存中有结果
            y = c2;
        } else {
            //缓存中没有结果
            y = fibonacci(n - 2, cache);
            //缓存结果
            cache[n - 2] = y;
        }

        return x + y;
    }
}
